import java.util.ArrayList;

public class PrimsMST {

	class Edge{
		int tail;
		int head;
		int weight;
	}
	
	class Vertex implements HeapItem{
		int heapIndex;
		int value;
		Edge curEdge;
		ArrayList<Edge> Edges;	
		
		Vertex(){
			heapIndex = -1;
			curEdge = null;
			value = 0X7FFFFFFF;
		}
		
		public void PrintData(){
			System.out.print("HeapIndex: " + heapIndex + " ");
			System.out.print("curEdge: " + curEdge + " ");
			System.out.print("value: " + value + " ");
		}
		
		public boolean isLargerThan(HeapItem vertex){			
			if(vertex instanceof Vertex)
				return (this.value > ((Vertex)vertex).value);
			else
				throw new IllegalArgumentException("not instance of Vertex");
		}
		
		
		public boolean isLessThan(HeapItem vertex){
			if(vertex instanceof Vertex)
				return (this.value < ((Vertex)vertex).value);
			else
				throw new IllegalArgumentException("not instance of Vertex");
		}
		
		public void setHeapIndex(int index){
			heapIndex = index;
		}
		public int getHeapIndex(){
			return heapIndex;
		}
	}
	
	private ArrayList<Vertex> vertices;
	private ArrayList<Edge> minSpanTree;
	private THeap<Vertex> verticesHeap;
	
	
	public void InitData(){
		DataReader reader = new DataReader();
		reader.SetFilename("D:\\algorithm\\part2\\wk1\\edges.txt");
		
		String str;
		str = reader.GetNextLine();
		String[] parser = str.split(" ");
		int count = Integer.parseInt(parser[0]);
		vertices = new ArrayList<Vertex>(count);
		for(int i = 0; i < count; i++)
		{
			Vertex ver = new Vertex();
			vertices.add(ver);
			ver.Edges = new ArrayList<Edge>();
		}
		
		while((str = reader.GetNextLine()) != null)
		{
			parser = str.split(" ");
			int verIndex = Integer.parseInt(parser[0]) - 1; 
			
			Vertex ver = vertices.get(verIndex);
			if(ver == null)
			{
				throw new NullPointerException("null pointer");
			}
			
			Edge e = new Edge();
			e.tail = verIndex + 1;
			e.head = Integer.parseInt(parser[1]);
			e.weight = Integer.parseInt(parser[2]);
			ver.Edges.add(e);
			
			verIndex = e.head - 1;
			ver = vertices.get(verIndex);
			Edge e2 = new Edge();
			e2.tail = e.head;
			e2.head = e.tail;
			e2.weight = e.weight;
			ver.Edges.add(e2);
		}
	}
	
	
	
	public void ConstructHeap(){
		verticesHeap = new THeap<Vertex>(vertices.size());
		
		for(int i = 1; i < vertices.size(); i++)
		{
			Vertex ver = vertices.get(i);
			verticesHeap.Insert(ver);
		}
	}
	
	
	
	public void UpdateHeap(int head, int source){
		Vertex verUpdate = vertices.get(head - 1);
		if(verUpdate.getHeapIndex() == -1)
			return;
		
		for(int i = 0; i < verUpdate.Edges.size(); i++)
		{
			Edge e = verUpdate.Edges.get(i);
			if(e.head == source){
				if(verUpdate.value > e.weight)
				{
					verUpdate.value = e.weight;
					verUpdate.curEdge = e;
					verticesHeap.UpdatePosition(verUpdate.getHeapIndex());					
				}
				break;
			}
		}
	}
	
	public void RunPrim(){
		ConstructHeap();
		
		Vertex ver = vertices.get(0);
		minSpanTree = new ArrayList<Edge>();
		
		for(int i = 0; i < ver.Edges.size(); i++)
		{
			Edge e = ver.Edges.get(i);
			
			//update value of Vertex e.head - 1;
			UpdateHeap(e.head, e.tail);			
		}
		
		
		while(verticesHeap.Size() > 0)
		{
			ver = verticesHeap.ExtractMin();
			minSpanTree.add(ver.curEdge);
			ver.setHeapIndex(-1);
			//Update all veritces which connect to ver
			for(int i = 0; i < ver.Edges.size(); i++)
			{
				Edge e = ver.Edges.get(i);
				
				UpdateHeap(e.head, e.tail);
			}
		}		
		
	}
	
	
	
	public void PrintData(){
		
		System.out.println("vertices are:");
		for(int i = 0; i < vertices.size(); i++)
		{
			Vertex ver = vertices.get(i);
			System.out.print((i+1) + " " + ver.heapIndex + " " + ver.value + " ");
			for(int j = 0; j < ver.Edges.size(); j++)
			{
				Edge edge = ver.Edges.get(j);
				System.out.print(" " + edge.head + " " + edge.weight);
			}
			System.out.print("\n");
		}
		
		System.out.println("Heap data is: ");
		verticesHeap.PrintData();
		
		System.out.println("Minimum Span Tree is :");
		long totalWeight = 0;
		for(int i = 0; i < minSpanTree.size(); i++)
		{
			Edge e = minSpanTree.get(i);
			totalWeight += e.weight;
			System.out.print("Edge " + (i + 1) + e.tail+"->" + e.head + " " + e.weight + "\n");
		}	
		System.out.println("MST is " + totalWeight);
	}
	
	

}
